package GBP;

import java.util.*;

/*
 * Individual.java
 * Created: 2005-12-23 22:40
 */
/**
 * An array-based implementation of Individual 
 *  for Graph-Bipartitioning Problems.
 * @author T.S.Yo
**/

public class Individual implements Cloneable,Comparator<Individual>
{
    private String name = "GBP individual";
    private int arraySize = 500;        // The default size of the geno-array
    private int[] gt;                   // The chromosome: an array of gene 
    private int fitness = 0;            // The value of fitness 
    private boolean evaluated = false;  // The flag indicate if this individual is evaluated
    private GraphDef gDef;              // The graph definition

//---------------------------------------------------------------------
// Constructor    
    /** Random Constructor **/
//    public Individual(final GraphDef gbp){
//        randGene();
//        gDef = gbp;
//        evalInd();
//    }
    /** Random Constructor with given size**/
    public Individual(final int size, final GraphDef gbp){
        arraySize = size;
        randGene();
        gDef = gbp;
        evalInd();
    }
    /** Copy Constructor **/
    public Individual(final Individual ind){
        arraySize = ind.getArraySize();
        gt = new int[arraySize];
        setGenes(ind.getGenes());
        gDef = ind.getGDef();
        fitness = ind.getFitness();
        evaluated = true;
    }
//---------------------------------------------------------------------
// Methods to access private members    
    // arraySize: 
    /** Returning the size of the bit array **/
    public int getArraySize(){
        return arraySize;
    }
    /** The arraySize cannot be changed after initialization **/
    public void setArraySize(int newSize){
        System.out.println("The arraySize cannot be changed after initialization");
    }
    
    // gt: 
    /** Randomly generate an array of Genotype **/
    public void randGene(){
        // An array with 250 '0's and 250 '1's
        //System.out.println("    Initializing individual with size:  "+arraySize);   // For testing
        gt = new int[arraySize];
        // gt[0]~gt[249] = 0
        //System.out.println("    Initializing first half:  0 ~ "+((arraySize/2)-1));   // For testing
        for(int i = 0; i < (arraySize/2); i++){
            gt[i] = 0;
        }
        // gt[250]~gt[499] = 1
        //System.out.println("    Initializing second half:  "+((arraySize/2)-1)+" ~ "+(arraySize-1));   // For testing
        for(int i = arraySize/2; i < arraySize; i++){
            gt[i] = 1;
        }
        // Random permutation
        //System.out.println("    Start random permutation");    // For testing
        Random rand = new Random();
        for(int i = 0; i < (arraySize-1); i++){
            // j = random number within [ i, arraySize ]
            int j = rand.nextInt((arraySize-i)) + i;
            // Swap gt[i] and gt[j]
            //System.out.println("      Swap "+i+" and "+j);     // For testing
            int tmp = gt[i];
            gt[i] = gt[j];
            gt[j] = tmp;
        }
    }
    /** Retrieving gt **/
    public int[] getGenes(){
        return gt;
    }
    /** Replacing the the whole gt **/
    public void setGenes(final int[] oriGenes){
        for (int i = 0; i < arraySize; i++){
            this.gt[i] = oriGenes[i];
        }
        this.evaluated = false;
    }
    /** Modifying the gt **/
    public void setGene(final int position, final int gene){
        this.gt[position] = gene;
        this.evaluated = false;
    }

    // Fitness and evaluated 
    /** evaluate the individual **/
    public void evalInd(){
        this.fitness = calFitness();
        this.evaluated = true;
    }
    /** Returning evaluation **/
    public int getFitness(){
        if (this.evaluated){
            return this.fitness;
        }else{
            //System.out.println("    Individual is not evaluated, recompute fitness....");    // For testing
            evalInd();
            return this.fitness;
        }
    }

    // graph definition 
    /** Setting graph definition **/
    public void setGDef(final GraphDef gbp){
        System.out.println("The graph definition cannot be changed after initialization");
    }
    /** Returning the graph definition **/
    public GraphDef getGDef(){
        return this.gDef;
    }
//---------------------------------------------------------------------
// Overriding toString() to show the gt
    /** Overriding the toString()  method to show the content of the individual **/
    public String toString(){
        //String group0 = "\n    Group0: ";
        //String group1 = "\n    Group1: ";
        String output = new String("    "+name+"\n");
        for (int i = 0; i < arraySize; i++){
           output = output + " " + gt[i];
           if((i%25)==24) output = output + "\n";
           //switch(gt[i]){
           // case 0:
           //     group0 = group0 + " " + (i+1);
           //     break;
           // case 1:
           //     group1 = group1 + " " + (i+1);
           //     break;
           //}
        } 
        //output = output + group0;
        //output = output + group1; 
        output = output + " \nFitness: " + this.getFitness();
        return(output);
    }
    
    /** Overriding the comparator between Individuals  **/
    public int compareTo(final Individual ind){
        int comp = 0;
        if (this.fitness!=ind.getFitness()){
            return (int)(this.fitness-ind.getFitness());
        } else {
            for (int i = 0; i < arraySize; i++){
                if (gt[i] != ind.getGenes()[i]){
                    comp = gt[i] - ind.getGenes()[i];
                    break;
                }
            }
            return comp;
        }
    }
//
// Implementing the Comparator
    public int compare(Individual ind1, Individual ind2){
        return (ind1.compareTo(ind2));
    }
    public boolean equals(Individual ind1, Individual ind2){
        return (ind1.compareTo(ind2)==0);
    }
// Methods for Cloneable    
    /** Implementing clone() **/    public Object clone(){
        try {
            return super.clone();
        } catch (CloneNotSupportedException e) {
            throw new Error("This should not occur since we implement Cloneable");
        }
    }
//---------------------------------------------------------------------
// Evaluating the individual    /** The fitness of this individual : cutSize, the smaller the better **/
    private int calFitness(){
        int cutSize = 0;
        for (int i = 0; i < arraySize; i++){           // Iterating through all nodes
            if(gt[i]==0){                              // Check only one group, avoid double counting
            
            int nodeID = gDef.graph[i].getId();         // ID of this node
            int nNb = gDef.graph[i].getNumNeighbors();  // 
            int[] nbs = gDef.graph[i].getNeighbors();   // All neighbors of this node
            
            for (int j = 0; j < nNb; j++){
                if(gt[(nodeID-1)]!= gt[(nbs[j]-1)]){   // If not in the same partition
                    cutSize++;                         // Add 1 to cutSize
                }
            }
            }
        }
        return -1*cutSize;        // returning -1*cutSize
    }
}